package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-17 18:43
 * @Description: JumpGame$55-跳跃游戏-https://leetcode-cn.com/problems/jump-game/
 */
public class JumpGame {

	/**
	 * 给定一个非负整数数组，你最初位于数组的第一个位置。
	 *
	 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
	 *
	 * 判断你是否能够到达最后一个位置。
	 *
	 * 示例 1:
	 *
	 * 输入: [2,3,1,1,4]
	 * 输出: true
	 * 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
	 * 示例 2:
	 *
	 * 输入: [3,2,1,0,4]
	 * 输出: false
	 * 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/jump-game
	 *
	 *
	 * 确定状态：最后一步在a(i)跳过来的，需要满足：
	 *      1.青蛙能跳到ai (i<n-1)
	 *      2.ai>=n-i-1
	 *   子问题：
	 *      状态为f[j],青蛙能不能跳到石头j,使用布尔数组表示
	 * 转移方程：
	 *      OR(0<=i<=j)(f[i]AND(i+a[i]></=j)
	 *
	 */

	public boolean canJump(int[] nums) {
		if(nums==null || nums.length==0){
			return false;
		}
		int n = nums.length;
		boolean[] f = new boolean[n];
		// 初始化，
		f[0] = true;
		for (int i = 1; i < n; i++) {
			// previous stone (last step)
			// set false first,任意解就设置为true
			f[i] = false;
			// 枚举0-i之间所有可能，能不能跳到ai，能不能跳到最后一块
			for (int j = 0; j < i; j++) {
				if(f[j]&&j+nums[j]>=i){
					f[i] = true;
					break;
				}
			}
		}
		return f[n-1];
	}

	public static void main(String[] args) {
      int[] nums = {1,3,4,1,4};
      JumpGame instance = new JumpGame();
      System.out.println(instance.canJump(nums));
      int[] nums2 = {3,2,1,0,4};
      System.out.println(instance.canJump(nums2));
	}
}
